package LeetCode._02算法基础.day01二分查找;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022 - 03 - 11 - 17:37
 * @Description 给定一个按照升序排列的整数数组 nums，和一个目标值 target。
 * 找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * @Version 中等
 */
public class _34有序数组中寻找目标值 {
    static int[] nums = {5,7,7,8,8,10};
    @Test
    public void solve(){

    }
    /*by me 二分查找 找到一个目标值下标再向两端找范围*/
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = -1;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(nums[mid] == target){
                break;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        //没找到
        if(left > right){
            return new int[]{-1, -1};
        }
        //找范围
        left = mid;
        right = mid;
        while(left >= 0 && nums[left] == target){
            left--;
        }
        while(right < nums.length && nums[right] == target){
            right++;
        }
        return new int[]{left + 1, right - 1};
    }
    /*官方思路*/
    public int[] searchRange1(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }
    /*
    二分查找中：
    寻找leftIdx 即为在数组中寻找第一个大于等于target 的下标
    寻找rightIdx 即为在数组中寻找第一个大于target 的下标，然后将下标减1。
     */
    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
